package sorting;

public class HeapSort {

	static int[] array = new int[] { 5, 9, 4, 0, 14, 6, 14, 99, 3, 44, 17 };

	public static void main(String[] args) {
		
		makeHeap(array);
		
		heapSort(array);

		printArray(array);

	}

	private static void heapSort(int[] array) {

		for (int i=array.length-1; i>0; i--) {
			int tmp = array[0];
			array[0] = array[i];
			array[i] = tmp;
			heapify(0, i-1);
		}
	}

	private static void makeHeap(int[] array) {

		for(int i=(array.length/2)-1; i>=0;i--) {
			heapify(i, array.length-1);			
		}
		
	}

	private static void heapify(int i, int length) {
		
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		
		int value = array[i];
		int max = i;
		if(l <= length && array[l] > value) {
			max = l;
			value = array[l];
		}
		
		if(r <= length && array[r] > value) {
			max = r;
			value = array[r];
		}
		
		if(i != max) {
			int tmp = array[i];
			array[i] = value;
			array[max] = tmp;
			
			heapify(max, length);
		}
		
	}

	private static void printArray(int[] array2) {
		for (int a : array) {
			System.out.print(a + " ");
		}
	}
}
